//有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。 
//
// 跳蚤跳跃的规则如下： 
//
// 
// 它可以 往前 跳恰好 a 个位置（即往右跳）。 
// 它可以 往后 跳恰好 b 个位置（即往左跳）。 
// 它不能 连续 往后跳 2 次。 
// 它不能跳到任何 forbidden 数组中的位置。 
// 
//
// 跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。 
//
// 给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃
//次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
//输出：3
//解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。
// 
//
// 示例 2： 
//
// 
//输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
//输出：-1
// 
//
// 示例 3： 
//
// 
//输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
//输出：2
//解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= forbidden.length <= 1000 
// 1 <= a, b, forbidden[i] <= 2000 
// 0 <= x <= 2000 
// forbidden 中所有位置互不相同。 
// 位置 x 不在 forbidden 中。 
// 
// Related Topics广度优先搜索 | 数组 | 动态规划 
//
// 👍 60, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class MinimumJumpsToReachHome {
    public static void main(String[] args) {
        Solution solution = new MinimumJumpsToReachHome().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // BFS
        // https://leetcode.cn/problems/minimum-jumps-to-reach-home/solution/yan-du-you-xian-sou-suo-ji-yi-hua-shen-s-265w/
        /*public int minimumJumps(int[] forbidden, int a, int b, int x) {
            // 向前跳，向后跳，搜索的最大距离应该是 x + a + b ，根据a,b的范围，开辟为6000，具体参照下面链接证明
            // https://leetcode.cn/problems/minimum-jumps-to-reach-home/solution/dao-jia-de-zui-shao-tiao-yue-ci-shu-zui-duan-lu-zh/
            int limit = 6000;
            // 第一维表示当前搜索的位置，第二维表示是第几次向左跳，题目固定向左跳只能跳一次
            boolean[][] visited = new boolean[limit + 1][2];
            // 保存禁止跳的位置
            Set<Integer> set = new HashSet<>();
            for (int i : forbidden) set.add(i);
            Queue<int[]> queue = new LinkedList<>();    // int[当前位置，向后跳次数]
            queue.offer(new int[]{0, 0});
            int step = -1;
            while (!queue.isEmpty()) {
                int size = queue.size();
                step++;
                for (int i = 0; i < size; i++) {
                    int[] poll = queue.poll();
                    int cur = poll[0], count = poll[1];
                    // 到达了家
                    if (cur == x) return step;
                    // 走过的位置直接跳过
                    if (visited[cur][count]) continue;

                    visited[cur][count] = true;

                    // 向右跳
                    if (cur + a <= limit && !set.contains(cur + a)) {
                        // 注意向左跳次数要设置为0，因为下个节点还没有往左跳过
                        queue.offer(new int[]{cur + a, 0});
                    }

                    // 向左跳
                    if (cur - b >= 0 && count < 1 && !set.contains(cur - b)) {
                        queue.offer(new int[]{cur - b, count + 1});
                    }
                }
            }

            return -1;
        }*/

        // DFS
        int limit = 6000, forwardStep, backStep;
        boolean[][] visited;
        Long[][] memo;   // 备忘录

        public int minimumJumps(int[] forbidden, int a, int b, int x) {
            this.visited = new boolean[limit + 1][2];
            this.memo = new Long[limit + 1][2];
            this.forwardStep = a;
            this.backStep = b;
            // 保存禁止跳的位置
            Set<Integer> set = new HashSet<>();
            for (int i : forbidden) set.add(i);
            long res = dfs(0, x, set, 0);
            return res == Integer.MAX_VALUE ? -1 : (int)res;
        }

        public long dfs(int cur, int tar, Set<Integer> set, int backCount) {
            if (memo[cur][backCount] != null) return memo[cur][backCount];
            if (cur == tar) return 0;
            visited[cur][backCount] = true;
            long res = Integer.MAX_VALUE;
            if (cur + forwardStep <= limit && !set.contains(cur + forwardStep) && !visited[cur + forwardStep][0]) {
                res = Math.min(res, 1 + dfs(cur + forwardStep, tar, set, 0));
            }

            if (cur - backStep >= 0 && backCount < 1 && !set.contains(cur - backStep) && !visited[cur - backStep][backCount + 1]) {
                res = Math.min(res, 1 + dfs(cur - backStep, tar, set, backCount + 1));
            }

            memo[cur][backCount] = res;
            return res;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
